#region Copyright

// The contents of this file are subject to the Mozilla Public License
//  Version 1.1 (the "License"); you may not use this file except in compliance
//  with the License. You may obtain a copy of the License at
//  
//  http://www.mozilla.org/MPL/
//  
//  Software distributed under the License is distributed on an "AS IS"
//  basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
//  License for the specific language governing rights and limitations under 
//  the License.
//  
//  The Initial Developer of the Original Code is Robert Smyth.
//  Portions created by Robert Smyth are Copyright (C) 2008.
//  
//  All Rights Reserved.

#endregion

using System;
using System.Collections.Generic;
using NUnit.Extensions.NUnitGridRunner.Metrics;
using NUnitGridThreadRunner.Alchemi.Metrics;


namespace NUnit.Extensions.NUnitGridRunner
{
    public class FixtureLoadLeveler
    {
        private readonly BucketList<IFixtureMetrics, TimeSpan> bucketList;
        private readonly string[] fixtureNames;
        private readonly int maximumFixturesPerThread = 100;
        private readonly TimeSpan runnerTimeLoading;
        private readonly ISuiteMetrics suiteMetics;
        private readonly ITextOutput textOutput;

        public FixtureLoadLeveler(ISuiteMetrics suiteMetics, ITextOutput textOutput, string[] fixtureNames,
                                  TimeSpan runnerTimeLoading)
        {
            this.suiteMetics = suiteMetics;
            this.textOutput = textOutput;
            this.fixtureNames = fixtureNames;
            this.runnerTimeLoading = runnerTimeLoading;
            bucketList =
                new BucketList<IFixtureMetrics, TimeSpan>(new FixtureRunTimeIndexer(runnerTimeLoading), 32);
        }

        public string[][] LeveledFixtures
        {
            get { return LevelFixtures(); }
        }

        private string[][] LevelFixtures()
        {
            var unresolvedFixtures = new List<IFixtureMetrics>();
            bucketList.Clear();
            foreach (string fixtureName in fixtureNames)
            {
                IFixtureMetrics fixtureMetrics = suiteMetics.GetMetrics(fixtureName);
                bucketList.Add(fixtureMetrics);
                unresolvedFixtures.Add(fixtureMetrics);
            }

            var gridThreadFixtures = new List<string[]>();
            while (unresolvedFixtures.Count > 0)
            {
                List<string> testFixturesToRun =
                    GetTestFixturesForNextGridThread(unresolvedFixtures, gridThreadFixtures);
                gridThreadFixtures.Add(testFixturesToRun.ToArray());
            }

            return gridThreadFixtures.ToArray();
        }

        private List<string> GetTestFixturesForNextGridThread(ICollection<IFixtureMetrics> unresolvedFixtures,
                                                              ICollection<string[]> executorFixtures)
        {
            textOutput.Verbose.WriteLine("  Grid runner #{0} expected run times:", executorFixtures.Count + 1);

            var testFixturesToRun = new List<string>();
            IFixtureMetrics fixtureMetrics = bucketList.GetNextLessThanOrEqualTo(runnerTimeLoading);
            LoadFixture(fixtureMetrics, unresolvedFixtures, testFixturesToRun);
            TimeSpan expectedRunTime = fixtureMetrics.RunTime;

            while (expectedRunTime < runnerTimeLoading && unresolvedFixtures.Count > 0 &&
                   testFixturesToRun.Count < maximumFixturesPerThread)
            {
                fixtureMetrics = bucketList.GetNextLessThanOrEqualTo(runnerTimeLoading - expectedRunTime);
                if (fixtureMetrics == null)
                {
                    break;
                }
                LoadFixture(fixtureMetrics, unresolvedFixtures, testFixturesToRun);
                expectedRunTime += fixtureMetrics.RunTime;
            }

            textOutput.Verbose.WriteLine("   {0} Total.\n", expectedRunTime);
            return testFixturesToRun;
        }

        private void LoadFixture(IFixtureMetrics testFixture, ICollection<IFixtureMetrics> unresolvedFixtures,
                                 ICollection<string> testFixturesToRun)
        {
            unresolvedFixtures.Remove(testFixture);
            bucketList.Remove(testFixture);

            testFixturesToRun.Add(testFixture.FixtureName);
            textOutput.Verbose.WriteLine("   {1} '{0}'.", testFixture.FixtureName, testFixture.RunTime);
        }
    }

    public class BucketList<T1, T2>
        where T1 : class
    {
        private readonly List<T1>[] buckets;
        private readonly IBucketIndexer<T1, T2> indexer;
        private readonly int numberOfBuckets;

        public BucketList(IBucketIndexer<T1, T2> indexer, int numberOfBuckets)
        {
            this.indexer = indexer;
            this.numberOfBuckets = numberOfBuckets;
            buckets = new List<T1>[numberOfBuckets];
            for (int bucketIndex = 0; bucketIndex < buckets.Length; bucketIndex++)
            {
                buckets[bucketIndex] = new List<T1>();
            }
        }

        public void AddRange(T1[] items)
        {
            foreach (T1 item in items)
            {
                Add(item);
            }
        }

        public void Add(T1 item)
        {
            double rank = indexer.GetRank(item);
            buckets[GetBucketIndex(rank)].Add(item);
        }

        public void Remove(T1 item)
        {
            double rank = indexer.GetRank(item);
            buckets[GetBucketIndex(rank)].Remove(item);
        }

        public T1 GetNextLessThanOrEqualTo(T2 upperValue)
        {
            T1 item = null;
            double rank = indexer.GetRank(upperValue);
            for (int bucketIndex = GetBucketIndex(rank); bucketIndex >= 0; bucketIndex--)
            {
                if (buckets[bucketIndex].Count > 0)
                {
                    item = buckets[bucketIndex][0];
                    break;
                }
            }
            return item;
        }

        private int GetBucketIndex(double rank)
        {
            var bucketIndex = (int) (numberOfBuckets*rank);
            if (bucketIndex >= buckets.Length)
            {
                bucketIndex = buckets.Length - 1;
            }
            return bucketIndex;
        }

        public void Clear()
        {
            foreach (List<T1> bucket in buckets)
            {
                bucket.Clear();
            }
        }
    }

    public interface IBucketIndexer<T1, T2>
    {
        double GetRank(T1 item);
        double GetRank(T2 item);
    }

    public class FixtureRunTimeIndexer : IBucketIndexer<IFixtureMetrics, TimeSpan>
    {
        private readonly TimeSpan maxTime;

        public FixtureRunTimeIndexer(TimeSpan maxTime)
        {
            this.maxTime = maxTime;
        }

        double IBucketIndexer<IFixtureMetrics, TimeSpan>.GetRank(IFixtureMetrics item)
        {
            return item.RunTime.TotalMilliseconds/maxTime.TotalMilliseconds;
        }

        double IBucketIndexer<IFixtureMetrics, TimeSpan>.GetRank(TimeSpan item)
        {
            return item.TotalMilliseconds/maxTime.TotalMilliseconds;
        }
    }
}